7860. Судейские проблемы

Организаторы NWERC решили, что они хотят улучшить автоматическую оценку посылок в конкурсе, поэтому теперь они используют две системы: DOMjudge и Kattis. Каждая посылка оценивается обеими системами, и результаты оценки сравниваются, чтобы удостовериться, что системы согласованы. Тем не менее, что-то пошло не так в настройке связи между системами, и теперь жюри знает только все результаты обеих систем, но не результат каждой отправки! Поэтому Вас просят помочь выяснить, сколько могло быть корректных результатов.

Вход. Состоит из:

· одно число n (1 ≤ n ≤ 10⁵) – количество посылок;

· n строк, каждая из которых дает результат судейства DOMjudge системы, в произвольном порядке;

· n строк, каждая из которых дает результат судейства Kattis системы, в произвольном порядке.

Каждый результат представляет собой строку длины между 5 и 15 символами (включительно), состоящих из строчных букв.

Выход. Выведите максимальное количество результатов, которое были бы одинаковыми для обеих систем.

Пример входа	Пример выхода
5 correct wronganswer correct correct timelimit wronganswer correct timelimit correct timelimit	4

РЕШЕНИЕ

структуры данных

Анализ алгоритма

В задаче следует подсчитать какие и сколько результатов судейства были получены системами DOMjudge и Kattis. Если результат s системой DOMjudge был получен a раз, а системой Kattis b раз, то количество одинаковых результатов s равно min(a, b).

Подсчитаем в отображении map<string, int> cnt количество результатов s, которые выдала система DOMjudge. Далее для каждого результата s системы Kattis уменьшим значение cnt[s] на единицу (если cnt[s] > 0). Подсчитаем количество таких уменьшений – оно и равно максимальному количеству результатов, которые были одинаковыми для обеих систем.

Пример

Подсчитаем количество результатов системами DOMjudge и Kattis в заданном примере.

Одинаковыми в системах были 4 результата.

Реализация алгоритма

Объявим отображение cnt, где cnt[s] хранит количество результатов s, которые выдала система DOMjudge.

map<string, int> cnt;

Читаем количество посылок n.

scanf("%d\n", &n);

Подсчитываем количество результатов системы DOMjudge.

for (i = 0; i < n; i++)

{

gets(s);

cnt[s]++;

}

Обрабатываем результаты системы Kattis.

res = 0;

for (i = 0; i < n; i++)

{

gets(s);

Если результат s встречался в DOMjudge (cnt[s] > 0), то уменьшаем cnt[s] на единицу и увеличиваем счетчик результатов res, которые были бы одинаковыми для обеих систем.

if (cnt[s] > 0)

{

cnt[s]--;

res++;

}

}

Выводим ответ.

printf("%d\n", res);

Java реализация

import java.util.*;

public class Main

{

static Map<String, Integer> cnt = new HashMap<String, Integer>();

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

for(int i = 1; i <= n; i++)

{

String s = con.next();

if (!cnt.containsKey(s))

cnt.put(s, 1);

else

cnt.put(s, cnt.get(s) + 1);

}

int res = 0;

for(int i = 1; i <= n; i++)

{

String s = con.next();

if (cnt.containsKey(s) && cnt.get(s) > 0)

{

cnt.put(s, cnt.get(s) - 1);

res++;

}

}

System.out.print(res);

con.close();

}

}